/**
 * 
 */
package leetCode;

import java.util.HashSet;

/**
 * @author zhong
 *
 */
public class FairCandySwap {
	public int[] fairCandySwap(int[] A, int[] B) {
		// 把A存到hash中
		HashSet<Integer> set = new HashSet<>();

		for (int i : A) {
			set.add(i);
		}
		int sum1 = getSum(A);
		int sum2 = getSum(B);
		int avg = (sum1 + sum2) / 2;
		int diff = avg - sum1;
		// 找是否A中有B[j]-A[i]=diff
		for (int j : B) {
			if (set.contains(j - diff)) {
				return new int[] { j - diff, j };
			}
		}
		return null;
	}

	private int getSum(int[] a) {
		int sum = 0;
		for (int i : a) {
			sum += i;
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 1, 1 }, B = { 2, 2 };
		int[] res = new FairCandySwap().fairCandySwap(A, B);
		System.out.println(res[0]);
		System.out.println(res[1]);

	}

}
